package 力扣.周赛.蔚来;

public class 统计好数字的数目 {

//    一行版本
//     return (int) (Math.pow(5, n - n / 2) * Math.pow(4, n / 2)  % 1000000007);
//    50结果错误， 是 pow 溢出了。 需要使用快速幂
//    public int countGoodNumbers(long n) {
//         int res=0;
//         if (n%2==0){
//             int i = (int) (n / 2);
//             res= (int) (Math.pow(5,i)*Math.pow(4,i))%1000000007;
//             return  res;
//         }
//         else {
//             int i = (int) (n / 2);
//             res= (int) (Math.pow(5,i+1)*Math.pow(4,i))%1000000007;
//             return  res;
//         }
//    }
           static final long MOD=1000000007;
           public int countGoodNumbers(long n) {
               return (int)((fastPow(5,(n+1)/2)*fastPow(4,n/2))%MOD);
           }

         private long fastPow(long x, long n) {
               long res=1;
               while (n>0){
                   if (n%2==1)
                       res=(res*x)%MOD;
                   x=(x*x)%MOD;
                   n/=2;
               }
               return res;
         }
}
